package com.aqie.medium.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 386 字典序排数
 */
public class LexicalOrder {

    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        int index = 0, tmp = 0;
        // 获取迭代的深度
        while (tmp != 0){
            index++;
            tmp /= 10;
        }
        // 最外层从1开始
        for (int level = 1; level < 10; level++){
            if (n > level){
                res.add(level);
                insert(res, 0, index - 1, level, n);
            }else if (n == level){
                res.add(level);
                return res;
            }else {
                return res;
            }
        }
        return res;
    }

    private List<Integer> insert(List<Integer> list, int index, int stop, int base, int max) {
        if (index == stop) {
            for (int i = 0; i < 10; i++) {
                int cur = base * 10 + i;
                if (max > cur) {
                    list.add(cur);
                } else if (max == cur) {
                    list.add(cur);
                    return list;
                } else {
                    return list;
                }
            }
        } else {
            for (int i = 0; i < 10; i++) {
                int cur = base * 10 + i;
                if (max > cur) {
                    list.add(cur);
                    insert(list, index + 1, stop, cur, max);
                } else if (max == cur) {
                    list.add(cur);
                    return list;
                } else {
                    return list;
                }
            }
        }
        return list;

    }
}
